/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * 思维路径：
 *  1. a + b + c = 0 可以转化成 a + b = -c ,也就是求一个两数之和 = target
 *  2. -c 从哪里来？可以遍历每个item，每个都充当一次c => 第一层循环：固定c
 *  3. a 和 b 如何找相加等于-c?  会发现和-c很麻烦，因为c 现在已知，依然可以找 a + b + c = 0的关系
 *      - a + b + c > 0 如何移动？
 *      - a + b + c < 0 如何移动？
 *  4. 因为数据集是无序的，所以上述逻辑关系没有办法产生移动 a 或移动b 指针的行为，因此：
 *      - 将数组进行排序，那么a 指针指向固定元素的下一位
 *      - b指针指向数组的尾部，如下所示：
 * 
 *          a
 *    -4 || -1 -1 0 1 2
 *                    b
 * 
 *  5. 补充第三步：
 *       - 当a + b + c > 0 时，需要将b 往小（--）走，这样才能保证更接近结果。  
 *       - 当a + b + c < 0 时，需要将a 往大 (++)走，这样才能保证更接近结果。  
 *       - 当 ~~~ = 0 时，加入结果中。 各相向走一步
 * 
 *  6. 当a 和 b 指针"错位"后，结束本轮查找，将所固定的元素向前走一步。
 * 
 *  7. 重复上述过程，直到a 指针越界。
 * 
 *  会有什么问题？ !!重复元素!!
 * 
 * 关键点：去重方式和时机

 *  - 如果nums[c] === nums[c - 1] 说明有重复，直接continue 挡板行前走，直到不重复。[时机:c已经改变，并要进行下一轮查找]
 *    （之所以向后比较而不是向前比较，是为了当i到最后一个元素时，不越界）
 *  - 如果nums[a] === nums[a + 1] 说明有重复，直接continue [时机:加入到结果后，要过滤掉后面相邻的相同元素]
 *     (之所以向前比较，是因为极限情况只会发生"错位"，不会发生越界，并且a移动方向就是向前(++))
 *  - 如果nums[b] === nums[b - 1] 说明有重复，直接continue [时机:加入到结果后，要过滤掉后面相邻的相同元素]
 *     (之所以向后比较，是因为如果b就在屁股时，不会发生越界，并且b移动方向就是向后（--）)
 * 
 * 
 * 整体时间复杂度：O(n * n => n * 2)
 */
var threeSum = function (nums) {
  // 边界处理：nums.length < 3时候 或者 nums不存在时候 不需要进行，返回 ;
  if (nums === null || nums.length < 3) {
    return [];
  }
  let res = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    // i 上述c 指针
    let L = i + 1, // L 上述a 指针
      R = nums.length - 1, // R 上述b 指针
      sum = -1;
    if (i > 0 && nums[i] === nums[i - 1]) continue; //c 去重时机
    while (L < R) {
      sum = nums[i] + nums[L] + nums[R];
      if (sum === 0) {
        res.push([nums[i], nums[L], nums[R]]);
        while (nums[L] === nums[L + 1]) L++; //a 去重时机
        while (nums[R] === nums[R - 1]) R--; //b 去重时机
        L++;
        R--;
      } else if (sum < 0) {
        L++;
      } else {
        R--;
      }
    }
  }
  return res;
};
